<html><head>
	<title>java测试</title>
	<link rel="stylesheet" type="text/css" href="./../../dist/modell-highLighter.css" />
	</head>
	<body><fieldset class="modell-highlighter"><legend>Java 代码</legend><pre><ol class="code_list"><li><span class="comment">/*</span></li><li><span class="comment"> * Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved.</span></li><li><span class="comment"> * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> *</span></li><li><span class="comment"> */</span></li><li></li><li><span class="keyword">package</span> java.util;</li><li></li><li><span class="keyword">import</span> java.util.function.Consumer;</li><li><span class="keyword">import</span> java.util.function.Predicate;</li><li><span class="keyword">import</span> java.util.function.UnaryOperator;</li><li><span class="keyword">import</span> sun.misc.SharedSecrets;</li><li></li><li><span class="doc">/**</span></li><li><span class="doc"> * Resizable-array implementation of the &lt;tt&gt;List&lt;/tt&gt; interface.  Implements</span></li><li><span class="doc"> * all optional list operations, and permits all elements, including</span></li><li><span class="doc"> * &lt;tt&gt;null&lt;/tt&gt;.  In addition to implementing the &lt;tt&gt;List&lt;/tt&gt; interface,</span></li><li><span class="doc"> * this class provides methods to manipulate the size of the array that is</span></li><li><span class="doc"> * used internally to store the list.  (This class is roughly equivalent to</span></li><li><span class="doc"> * &lt;tt&gt;Vector&lt;/tt&gt;, except that it is unsynchronized.)</span></li><li><span class="doc"> *</span></li><li><span class="doc"> * &lt;p&gt;The &lt;tt&gt;size&lt;/tt&gt;, &lt;tt&gt;isEmpty&lt;/tt&gt;, &lt;tt&gt;get&lt;/tt&gt;, &lt;tt&gt;set&lt;/tt&gt;,</span></li><li><span class="doc"> * &lt;tt&gt;iterator&lt;/tt&gt;, and &lt;tt&gt;listIterator&lt;/tt&gt; operations run in constant</span></li><li><span class="doc"> * time.  The &lt;tt&gt;add&lt;/tt&gt; operation runs in &lt;i&gt;amortized constant time&lt;/i&gt;,</span></li><li><span class="doc"> * that is, adding n elements requires O(n) time.  All of the other operations</span></li><li><span class="doc"> * run in linear time (roughly speaking).  The constant factor is low compared</span></li><li><span class="doc"> * to that for the &lt;tt&gt;LinkedList&lt;/tt&gt; implementation.</span></li><li><span class="doc"> *</span></li><li><span class="doc"> * &lt;p&gt;Each &lt;tt&gt;ArrayList&lt;/tt&gt; instance has a &lt;i&gt;capacity&lt;/i&gt;.  The capacity is</span></li><li><span class="doc"> * the size of the array used to store the elements in the list.  It is always</span></li><li><span class="doc"> * at least as large as the list size.  As elements are added to an ArrayList,</span></li><li><span class="doc"> * its capacity grows automatically.  The details of the growth policy are not</span></li><li><span class="doc"> * specified beyond the fact that adding an element has constant amortized</span></li><li><span class="doc"> * time cost.</span></li><li><span class="doc"> *</span></li><li><span class="doc"> * &lt;p&gt;An application can increase the capacity of an &lt;tt&gt;ArrayList&lt;/tt&gt; instance</span></li><li><span class="doc"> * before adding a large number of elements using the &lt;tt&gt;ensureCapacity&lt;/tt&gt;</span></li><li><span class="doc"> * operation.  This may reduce the amount of incremental reallocation.</span></li><li><span class="doc"> *</span></li><li><span class="doc"> * &lt;p&gt;&lt;strong&gt;Note that this implementation is not synchronized.&lt;/strong&gt;</span></li><li><span class="doc"> * If multiple threads access an &lt;tt&gt;ArrayList&lt;/tt&gt; instance concurrently,</span></li><li><span class="doc"> * and at least one of the threads modifies the list structurally, it</span></li><li><span class="doc"> * &lt;i&gt;must&lt;/i&gt; be synchronized externally.  (A structural modification is</span></li><li><span class="doc"> * any operation that adds or deletes one or more elements, or explicitly</span></li><li><span class="doc"> * resizes the backing array; merely setting the value of an element is not</span></li><li><span class="doc"> * a structural modification.)  This is typically accomplished by</span></li><li><span class="doc"> * synchronizing on some object that naturally encapsulates the list.</span></li><li><span class="doc"> *</span></li><li><span class="doc"> * If no such object exists, the list should be &quot;wrapped&quot; using the</span></li><li><span class="doc"> * {@link Collections&#35;synchronizedList Collections.synchronizedList}</span></li><li><span class="doc"> * method.  This is best done at creation time, to prevent accidental</span></li><li><span class="doc"> * unsynchronized access to the list:&lt;pre&gt;</span></li><li><span class="doc"> *   List list = Collections.synchronizedList(new ArrayList(...));&lt;/pre&gt;</span></li><li><span class="doc"> *</span></li><li><span class="doc"> * &lt;p&gt;&lt;a name=&quot;fail-fast&quot;&gt;</span></li><li><span class="doc"> * The iterators returned by this class's {@link &#35;iterator() iterator} and</span></li><li><span class="doc"> * {@link &#35;listIterator(int) listIterator} methods are &lt;em&gt;fail-fast&lt;/em&gt;:&lt;/a&gt;</span></li><li><span class="doc"> * if the list is structurally modified at any time after the iterator is</span></li><li><span class="doc"> * created, in any way except through the iterator's own</span></li><li><span class="doc"> * {@link ListIterator&#35;remove() remove} or</span></li><li><span class="doc"> * {@link ListIterator&#35;add(Object) add} methods, the iterator will throw a</span></li><li><span class="doc"> * {@link ConcurrentModificationException}.  Thus, in the face of</span></li><li><span class="doc"> * concurrent modification, the iterator fails quickly and cleanly, rather</span></li><li><span class="doc"> * than risking arbitrary, non-deterministic behavior at an undetermined</span></li><li><span class="doc"> * time in the future.</span></li><li><span class="doc"> *</span></li><li><span class="doc"> * &lt;p&gt;Note that the fail-fast behavior of an iterator cannot be guaranteed</span></li><li><span class="doc"> * as it is, generally speaking, impossible to make any hard guarantees in the</span></li><li><span class="doc"> * presence of unsynchronized concurrent modification.  Fail-fast iterators</span></li><li><span class="doc"> * throw {@code ConcurrentModificationException} on a best-effort basis.</span></li><li><span class="doc"> * Therefore, it would be wrong to write a program that depended on this</span></li><li><span class="doc"> * exception for its correctness:  &lt;i&gt;the fail-fast behavior of iterators</span></li><li><span class="doc"> * should be used only to detect bugs.&lt;/i&gt;</span></li><li><span class="doc"> *</span></li><li><span class="doc"> * &lt;p&gt;This class is a member of the</span></li><li><span class="doc"> * &lt;a href=&quot;{@docRoot}/../technotes/guides/collections/index.html&quot;&gt;</span></li><li><span class="doc"> * Java Collections Framework&lt;/a&gt;.</span></li><li><span class="doc"> *</span></li><li><span class="doc"> * @author  Josh Bloch</span></li><li><span class="doc"> * @author  Neal Gafter</span></li><li><span class="doc"> * @see     Collection</span></li><li><span class="doc"> * @see     List</span></li><li><span class="doc"> * @see     LinkedList</span></li><li><span class="doc"> * @see     Vector</span></li><li><span class="doc"> * @since   1.2</span></li><li><span class="doc"> */</span></li><li></li><li><span class="keyword">public</span> <span class="keyword">class</span> ArrayList<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> <span class="keyword">extends</span> AbstractList<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span></li><li>        <span class="keyword">implements</span> List<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span>, RandomAccess, Cloneable, java.io.Serializable</li><li><span class="bracket">{</span></li><li>    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">long</span> serialVersionUID = <span class="number">8683452581122892189L</span>;</li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Default initial capacity.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> DEFAULT_CAPACITY = <span class="number">10</span>;</li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Shared empty array instance used for empty instances.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> Object<span class="bracket">[</span><span class="bracket">]</span> EMPTY_ELEMENTDATA = <span class="bracket">{</span><span class="bracket">}</span>;</li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Shared empty array instance used for default sized empty instances. We</span></li><li><span class="doc">     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when</span></li><li><span class="doc">     * first element is added.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> Object<span class="bracket">[</span><span class="bracket">]</span> DEFAULTCAPACITY_EMPTY_ELEMENTDATA = <span class="bracket">{</span><span class="bracket">}</span>;</li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * The array buffer into which the elements of the ArrayList are stored.</span></li><li><span class="doc">     * The capacity of the ArrayList is the length of this array buffer. Any</span></li><li><span class="doc">     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA</span></li><li><span class="doc">     * will be expanded to DEFAULT_CAPACITY when the first element is added.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">transient</span> Object<span class="bracket">[</span><span class="bracket">]</span> elementData; <span class="comment">// non-private to simplify nested class access</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * The size of the ArrayList (the number of elements it contains).</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @serial</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">int</span> size;</li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Constructs an empty list with the specified initial capacity.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param  initialCapacity  the initial capacity of the list</span></li><li><span class="doc">     * @throws IllegalArgumentException if the specified initial capacity</span></li><li><span class="doc">     *         is negative</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> ArrayList<span class="bracket">(</span><span class="keyword">int</span> initialCapacity<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>initialCapacity <span class="bracket">></span> <span class="number">0</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">this</span>.elementData = <span class="keyword">new</span> Object<span class="bracket">[</span>initialCapacity<span class="bracket">]</span>;</li><li>        <span class="bracket">}</span> <span class="keyword">else</span> <span class="keyword">if</span> <span class="bracket">(</span>initialCapacity == <span class="number">0</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">this</span>.elementData = EMPTY_ELEMENTDATA;</li><li>        <span class="bracket">}</span> <span class="keyword">else</span> <span class="bracket">{</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException<span class="bracket">(</span><span class="string">&quot;Illegal Capacity: &quot;</span>+</li><li>                                               initialCapacity<span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Constructs an empty list with an initial capacity of ten.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> ArrayList<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">this</span>.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Constructs a list containing the elements of the specified</span></li><li><span class="doc">     * collection, in the order they are returned by the collection's</span></li><li><span class="doc">     * iterator.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param c the collection whose elements are to be placed into this list</span></li><li><span class="doc">     * @throws NullPointerException if the specified collection is null</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> ArrayList<span class="bracket">(</span>Collection<span class="bracket"><</span>? <span class="keyword">extends</span> <span class="builtin_var">E</span><span class="bracket">></span> c<span class="bracket">)</span> <span class="bracket">{</span></li><li>        elementData = c.toArray<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span><span class="bracket">(</span>size = elementData.length<span class="bracket">)</span> != <span class="number">0</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="comment">// c.toArray might (incorrectly) not return Object[] (see 6260652)</span></li><li>            <span class="keyword">if</span> <span class="bracket">(</span>elementData.getClass<span class="bracket">(</span><span class="bracket">)</span> != Object<span class="bracket">[</span><span class="bracket">]</span>.<span class="keyword">class</span><span class="bracket">)</span></li><li>                elementData = Arrays.copyOf<span class="bracket">(</span>elementData, size, Object<span class="bracket">[</span><span class="bracket">]</span>.<span class="keyword">class</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span> <span class="keyword">else</span> <span class="bracket">{</span></li><li>            <span class="comment">// replace with empty array.</span></li><li>            <span class="keyword">this</span>.elementData = EMPTY_ELEMENTDATA;</li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Trims the capacity of this &lt;tt&gt;ArrayList&lt;/tt&gt; instance to be the</span></li><li><span class="doc">     * list's current size.  An application can use this operation to minimize</span></li><li><span class="doc">     * the storage of an &lt;tt&gt;ArrayList&lt;/tt&gt; instance.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">void</span> trimToSize<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>        modCount++;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span>size <span class="bracket"><</span> elementData.length<span class="bracket">)</span> <span class="bracket">{</span></li><li>            elementData = <span class="bracket">(</span>size == <span class="number">0</span><span class="bracket">)</span></li><li>              ? EMPTY_ELEMENTDATA</li><li>              : Arrays.copyOf<span class="bracket">(</span>elementData, size<span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Increases the capacity of this &lt;tt&gt;ArrayList&lt;/tt&gt; instance, if</span></li><li><span class="doc">     * necessary, to ensure that it can hold at least the number of elements</span></li><li><span class="doc">     * specified by the minimum capacity argument.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param   minCapacity   the desired minimum capacity</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">void</span> ensureCapacity<span class="bracket">(</span><span class="keyword">int</span> minCapacity<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">int</span> minExpand = <span class="bracket">(</span>elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA<span class="bracket">)</span></li><li>            <span class="comment">// any size if not default element table</span></li><li>            ? <span class="number">0</span></li><li>            <span class="comment">// larger than default for default empty table. It's already</span></li><li>            <span class="comment">// supposed to be at default size.</span></li><li>            : DEFAULT_CAPACITY;</li><li></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>minCapacity <span class="bracket">></span> minExpand<span class="bracket">)</span> <span class="bracket">{</span></li><li>            ensureExplicitCapacity<span class="bracket">(</span>minCapacity<span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">int</span> calculateCapacity<span class="bracket">(</span>Object<span class="bracket">[</span><span class="bracket">]</span> elementData, <span class="keyword">int</span> minCapacity<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">return</span> Math.max<span class="bracket">(</span>DEFAULT_CAPACITY, minCapacity<span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>        <span class="keyword">return</span> minCapacity;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="keyword">private</span> <span class="keyword">void</span> ensureCapacityInternal<span class="bracket">(</span><span class="keyword">int</span> minCapacity<span class="bracket">)</span> <span class="bracket">{</span></li><li>        ensureExplicitCapacity<span class="bracket">(</span>calculateCapacity<span class="bracket">(</span>elementData, minCapacity<span class="bracket">)</span><span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="keyword">private</span> <span class="keyword">void</span> ensureExplicitCapacity<span class="bracket">(</span><span class="keyword">int</span> minCapacity<span class="bracket">)</span> <span class="bracket">{</span></li><li>        modCount++;</li><li></li><li>        <span class="comment">// overflow-conscious code</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>minCapacity - elementData.length <span class="bracket">></span> <span class="number">0</span><span class="bracket">)</span></li><li>            grow<span class="bracket">(</span>minCapacity<span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * The maximum size of array to allocate.</span></li><li><span class="doc">     * Some VMs reserve some header words in an array.</span></li><li><span class="doc">     * Attempts to allocate larger arrays may result in</span></li><li><span class="doc">     * OutOfMemoryError: Requested array size exceeds VM limit</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MAX_ARRAY_SIZE = Integer.MAX_VALUE - <span class="number">8</span>;</li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Increases the capacity to ensure that it can hold at least the</span></li><li><span class="doc">     * number of elements specified by the minimum capacity argument.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param minCapacity the desired minimum capacity</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">void</span> grow<span class="bracket">(</span><span class="keyword">int</span> minCapacity<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="comment">// overflow-conscious code</span></li><li>        <span class="keyword">int</span> oldCapacity = elementData.length;</li><li>        <span class="keyword">int</span> newCapacity = oldCapacity + <span class="bracket">(</span>oldCapacity <span class="bracket">></span><span class="bracket">></span> <span class="number">1</span><span class="bracket">)</span>;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span>newCapacity - minCapacity <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span></li><li>            newCapacity = minCapacity;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span>newCapacity - MAX_ARRAY_SIZE <span class="bracket">></span> <span class="number">0</span><span class="bracket">)</span></li><li>            newCapacity = hugeCapacity<span class="bracket">(</span>minCapacity<span class="bracket">)</span>;</li><li>        <span class="comment">// minCapacity is usually close to size, so this is a win:</span></li><li>        elementData = Arrays.copyOf<span class="bracket">(</span>elementData, newCapacity<span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">int</span> hugeCapacity<span class="bracket">(</span><span class="keyword">int</span> minCapacity<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>minCapacity <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span> <span class="comment">// overflow</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> OutOfMemoryError<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="keyword">return</span> <span class="bracket">(</span>minCapacity <span class="bracket">></span> MAX_ARRAY_SIZE<span class="bracket">)</span> ?</li><li>            Integer.MAX_VALUE :</li><li>            MAX_ARRAY_SIZE;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns the number of elements in this list.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @return the number of elements in this list</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">int</span> size<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">return</span> size;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns &lt;tt&gt;true&lt;/tt&gt; if this list contains no elements.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @return &lt;tt&gt;true&lt;/tt&gt; if this list contains no elements</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">boolean</span> isEmpty<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">return</span> size == <span class="number">0</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns &lt;tt&gt;true&lt;/tt&gt; if this list contains the specified element.</span></li><li><span class="doc">     * More formally, returns &lt;tt&gt;true&lt;/tt&gt; if and only if this list contains</span></li><li><span class="doc">     * at least one element &lt;tt&gt;e&lt;/tt&gt; such that</span></li><li><span class="doc">     * &lt;tt&gt;(o==null&amp;nbsp;?&amp;nbsp;e==null&amp;nbsp;:&amp;nbsp;o.equals(e))&lt;/tt&gt;.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param o element whose presence in this list is to be tested</span></li><li><span class="doc">     * @return &lt;tt&gt;true&lt;/tt&gt; if this list contains the specified element</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">boolean</span> contains<span class="bracket">(</span>Object o<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">return</span> indexOf<span class="bracket">(</span>o<span class="bracket">)</span> <span class="bracket">></span>= <span class="number">0</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns the index of the first occurrence of the specified element</span></li><li><span class="doc">     * in this list, or -1 if this list does not contain the element.</span></li><li><span class="doc">     * More formally, returns the lowest index &lt;tt&gt;i&lt;/tt&gt; such that</span></li><li><span class="doc">     * &lt;tt&gt;(o==null&amp;nbsp;?&amp;nbsp;get(i)==null&amp;nbsp;:&amp;nbsp;o.equals(get(i)))&lt;/tt&gt;,</span></li><li><span class="doc">     * or -1 if there is no such index.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">int</span> indexOf<span class="bracket">(</span>Object o<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>o == <span class="keyword">null</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i = <span class="number">0</span>; i <span class="bracket"><</span> size; i++<span class="bracket">)</span></li><li>                <span class="keyword">if</span> <span class="bracket">(</span>elementData<span class="bracket">[</span>i<span class="bracket">]</span>==null<span class="bracket">)</span></li><li>                    <span class="keyword">return</span> i;</li><li>        <span class="bracket">}</span> <span class="keyword">else</span> <span class="bracket">{</span></li><li>            <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i = <span class="number">0</span>; i <span class="bracket"><</span> size; i++<span class="bracket">)</span></li><li>                <span class="keyword">if</span> <span class="bracket">(</span>o.equals<span class="bracket">(</span>elementData<span class="bracket">[</span>i<span class="bracket">]</span><span class="bracket">)</span><span class="bracket">)</span></li><li>                    <span class="keyword">return</span> i;</li><li>        <span class="bracket">}</span></li><li>        <span class="keyword">return</span> -<span class="number">1</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns the index of the last occurrence of the specified element</span></li><li><span class="doc">     * in this list, or -1 if this list does not contain the element.</span></li><li><span class="doc">     * More formally, returns the highest index &lt;tt&gt;i&lt;/tt&gt; such that</span></li><li><span class="doc">     * &lt;tt&gt;(o==null&amp;nbsp;?&amp;nbsp;get(i)==null&amp;nbsp;:&amp;nbsp;o.equals(get(i)))&lt;/tt&gt;,</span></li><li><span class="doc">     * or -1 if there is no such index.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">int</span> lastIndexOf<span class="bracket">(</span>Object o<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>o == <span class="keyword">null</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i = size-<span class="number">1</span>; i <span class="bracket">></span>= <span class="number">0</span>; i--<span class="bracket">)</span></li><li>                <span class="keyword">if</span> <span class="bracket">(</span>elementData<span class="bracket">[</span>i<span class="bracket">]</span>==null<span class="bracket">)</span></li><li>                    <span class="keyword">return</span> i;</li><li>        <span class="bracket">}</span> <span class="keyword">else</span> <span class="bracket">{</span></li><li>            <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i = size-<span class="number">1</span>; i <span class="bracket">></span>= <span class="number">0</span>; i--<span class="bracket">)</span></li><li>                <span class="keyword">if</span> <span class="bracket">(</span>o.equals<span class="bracket">(</span>elementData<span class="bracket">[</span>i<span class="bracket">]</span><span class="bracket">)</span><span class="bracket">)</span></li><li>                    <span class="keyword">return</span> i;</li><li>        <span class="bracket">}</span></li><li>        <span class="keyword">return</span> -<span class="number">1</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns a shallow copy of this &lt;tt&gt;ArrayList&lt;/tt&gt; instance.  (The</span></li><li><span class="doc">     * elements themselves are not copied.)</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @return a clone of this &lt;tt&gt;ArrayList&lt;/tt&gt; instance</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> Object clone<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">try</span> <span class="bracket">{</span></li><li>            ArrayList<span class="bracket"><</span>?<span class="bracket">></span> v = <span class="bracket">(</span>ArrayList<span class="bracket"><</span>?<span class="bracket">></span><span class="bracket">)</span> <span class="keyword">super</span>.clone<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            v.elementData = Arrays.copyOf<span class="bracket">(</span>elementData, size<span class="bracket">)</span>;</li><li>            v.modCount = <span class="number">0</span>;</li><li>            <span class="keyword">return</span> v;</li><li>        <span class="bracket">}</span> <span class="keyword">catch</span> <span class="bracket">(</span>CloneNotSupportedException e<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="comment">// this shouldn't happen, since we are Cloneable</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> InternalError<span class="bracket">(</span>e<span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns an array containing all of the elements in this list</span></li><li><span class="doc">     * in proper sequence (from first to last element).</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * &lt;p&gt;The returned array will be &quot;safe&quot; in that no references to it are</span></li><li><span class="doc">     * maintained by this list.  (In other words, this method must allocate</span></li><li><span class="doc">     * a new array).  The caller is thus free to modify the returned array.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * &lt;p&gt;This method acts as bridge between array-based and collection-based</span></li><li><span class="doc">     * APIs.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @return an array containing all of the elements in this list in</span></li><li><span class="doc">     *         proper sequence</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> Object<span class="bracket">[</span><span class="bracket">]</span> toArray<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">return</span> Arrays.copyOf<span class="bracket">(</span>elementData, size<span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns an array containing all of the elements in this list in proper</span></li><li><span class="doc">     * sequence (from first to last element); the runtime type of the returned</span></li><li><span class="doc">     * array is that of the specified array.  If the list fits in the</span></li><li><span class="doc">     * specified array, it is returned therein.  Otherwise, a new array is</span></li><li><span class="doc">     * allocated with the runtime type of the specified array and the size of</span></li><li><span class="doc">     * this list.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * &lt;p&gt;If the list fits in the specified array with room to spare</span></li><li><span class="doc">     * (i.e., the array has more elements than the list), the element in</span></li><li><span class="doc">     * the array immediately following the end of the collection is set to</span></li><li><span class="doc">     * &lt;tt&gt;null&lt;/tt&gt;.  (This is useful in determining the length of the</span></li><li><span class="doc">     * list &lt;i&gt;only&lt;/i&gt; if the caller knows that the list does not contain</span></li><li><span class="doc">     * any null elements.)</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param a the array into which the elements of the list are to</span></li><li><span class="doc">     *          be stored, if it is big enough; otherwise, a new array of the</span></li><li><span class="doc">     *          same runtime type is allocated for this purpose.</span></li><li><span class="doc">     * @return an array containing the elements of the list</span></li><li><span class="doc">     * @throws ArrayStoreException if the runtime type of the specified array</span></li><li><span class="doc">     *         is not a supertype of the runtime type of every element in</span></li><li><span class="doc">     *         this list</span></li><li><span class="doc">     * @throws NullPointerException if the specified array is null</span></li><li><span class="doc">     */</span></li><li>    <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>    <span class="keyword">public</span> <span class="bracket"><</span><span class="builtin_var">T</span><span class="bracket">></span> <span class="builtin_var">T</span><span class="bracket">[</span><span class="bracket">]</span> toArray<span class="bracket">(</span><span class="builtin_var">T</span><span class="bracket">[</span><span class="bracket">]</span> a<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>a.length <span class="bracket"><</span> size<span class="bracket">)</span></li><li>            <span class="comment">// Make a new array of a's runtime type, but my contents:</span></li><li>            <span class="keyword">return</span> <span class="bracket">(</span><span class="builtin_var">T</span><span class="bracket">[</span><span class="bracket">]</span><span class="bracket">)</span> Arrays.copyOf<span class="bracket">(</span>elementData, size, a.getClass<span class="bracket">(</span><span class="bracket">)</span><span class="bracket">)</span>;</li><li>        System.arraycopy<span class="bracket">(</span>elementData, <span class="number">0</span>, a, <span class="number">0</span>, size<span class="bracket">)</span>;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span>a.length <span class="bracket">></span> size<span class="bracket">)</span></li><li>            a<span class="bracket">[</span>size<span class="bracket">]</span> = <span class="keyword">null</span>;</li><li>        <span class="keyword">return</span> a;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="comment">// Positional Access Operations</span></li><li></li><li>    <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>    <span class="builtin_var">E</span> elementData<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">return</span> <span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">)</span> elementData<span class="bracket">[</span>index<span class="bracket">]</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns the element at the specified position in this list.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param  index index of the element to return</span></li><li><span class="doc">     * @return the element at the specified position in this list</span></li><li><span class="doc">     * @throws IndexOutOfBoundsException {@inheritDoc}</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="builtin_var">E</span> get<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>        rangeCheck<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li></li><li>        <span class="keyword">return</span> elementData<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Replaces the element at the specified position in this list with</span></li><li><span class="doc">     * the specified element.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param index index of the element to replace</span></li><li><span class="doc">     * @param element element to be stored at the specified position</span></li><li><span class="doc">     * @return the element previously at the specified position</span></li><li><span class="doc">     * @throws IndexOutOfBoundsException {@inheritDoc}</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="builtin_var">E</span> set<span class="bracket">(</span><span class="keyword">int</span> index, <span class="builtin_var">E</span> element<span class="bracket">)</span> <span class="bracket">{</span></li><li>        rangeCheck<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li></li><li>        <span class="builtin_var">E</span> oldValue = elementData<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li>        elementData<span class="bracket">[</span>index<span class="bracket">]</span> = element;</li><li>        <span class="keyword">return</span> oldValue;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Appends the specified element to the end of this list.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param e element to be appended to this list</span></li><li><span class="doc">     * @return &lt;tt&gt;true&lt;/tt&gt; (as specified by {@link Collection&#35;add})</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">boolean</span> add<span class="bracket">(</span><span class="builtin_var">E</span> e<span class="bracket">)</span> <span class="bracket">{</span></li><li>        ensureCapacityInternal<span class="bracket">(</span>size + <span class="number">1</span><span class="bracket">)</span>;  <span class="comment">// Increments modCount!!</span></li><li>        elementData<span class="bracket">[</span>size++<span class="bracket">]</span> = e;</li><li>        <span class="keyword">return</span> <span class="keyword">true</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Inserts the specified element at the specified position in this</span></li><li><span class="doc">     * list. Shifts the element currently at that position (if any) and</span></li><li><span class="doc">     * any subsequent elements to the right (adds one to their indices).</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param index index at which the specified element is to be inserted</span></li><li><span class="doc">     * @param element element to be inserted</span></li><li><span class="doc">     * @throws IndexOutOfBoundsException {@inheritDoc}</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">void</span> add<span class="bracket">(</span><span class="keyword">int</span> index, <span class="builtin_var">E</span> element<span class="bracket">)</span> <span class="bracket">{</span></li><li>        rangeCheckForAdd<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li></li><li>        ensureCapacityInternal<span class="bracket">(</span>size + <span class="number">1</span><span class="bracket">)</span>;  <span class="comment">// Increments modCount!!</span></li><li>        System.arraycopy<span class="bracket">(</span>elementData, index, elementData, index + <span class="number">1</span>,</li><li>                         size - index<span class="bracket">)</span>;</li><li>        elementData<span class="bracket">[</span>index<span class="bracket">]</span> = element;</li><li>        size++;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Removes the element at the specified position in this list.</span></li><li><span class="doc">     * Shifts any subsequent elements to the left (subtracts one from their</span></li><li><span class="doc">     * indices).</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param index the index of the element to be removed</span></li><li><span class="doc">     * @return the element that was removed from the list</span></li><li><span class="doc">     * @throws IndexOutOfBoundsException {@inheritDoc}</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="builtin_var">E</span> remove<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>        rangeCheck<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li></li><li>        modCount++;</li><li>        <span class="builtin_var">E</span> oldValue = elementData<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li></li><li>        <span class="keyword">int</span> numMoved = size - index - <span class="number">1</span>;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span>numMoved <span class="bracket">></span> <span class="number">0</span><span class="bracket">)</span></li><li>            System.arraycopy<span class="bracket">(</span>elementData, index+<span class="number">1</span>, elementData, index,</li><li>                             numMoved<span class="bracket">)</span>;</li><li>        elementData<span class="bracket">[</span>--size<span class="bracket">]</span> = <span class="keyword">null</span>; <span class="comment">// clear to let GC do its work</span></li><li></li><li>        <span class="keyword">return</span> oldValue;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Removes the first occurrence of the specified element from this list,</span></li><li><span class="doc">     * if it is present.  If the list does not contain the element, it is</span></li><li><span class="doc">     * unchanged.  More formally, removes the element with the lowest index</span></li><li><span class="doc">     * &lt;tt&gt;i&lt;/tt&gt; such that</span></li><li><span class="doc">     * &lt;tt&gt;(o==null&amp;nbsp;?&amp;nbsp;get(i)==null&amp;nbsp;:&amp;nbsp;o.equals(get(i)))&lt;/tt&gt;</span></li><li><span class="doc">     * (if such an element exists).  Returns &lt;tt&gt;true&lt;/tt&gt; if this list</span></li><li><span class="doc">     * contained the specified element (or equivalently, if this list</span></li><li><span class="doc">     * changed as a result of the call).</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param o element to be removed from this list, if present</span></li><li><span class="doc">     * @return &lt;tt&gt;true&lt;/tt&gt; if this list contained the specified element</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">boolean</span> remove<span class="bracket">(</span>Object o<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>o == <span class="keyword">null</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> index = <span class="number">0</span>; index <span class="bracket"><</span> size; index++<span class="bracket">)</span></li><li>                <span class="keyword">if</span> <span class="bracket">(</span>elementData<span class="bracket">[</span>index<span class="bracket">]</span> == <span class="keyword">null</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                    fastRemove<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li>                    <span class="keyword">return</span> <span class="keyword">true</span>;</li><li>                <span class="bracket">}</span></li><li>        <span class="bracket">}</span> <span class="keyword">else</span> <span class="bracket">{</span></li><li>            <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> index = <span class="number">0</span>; index <span class="bracket"><</span> size; index++<span class="bracket">)</span></li><li>                <span class="keyword">if</span> <span class="bracket">(</span>o.equals<span class="bracket">(</span>elementData<span class="bracket">[</span>index<span class="bracket">]</span><span class="bracket">)</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                    fastRemove<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li>                    <span class="keyword">return</span> <span class="keyword">true</span>;</li><li>                <span class="bracket">}</span></li><li>        <span class="bracket">}</span></li><li>        <span class="keyword">return</span> <span class="keyword">false</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="comment">/*</span></li><li><span class="comment">     * Private remove method that skips bounds checking and does not</span></li><li><span class="comment">     * return the value removed.</span></li><li><span class="comment">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">void</span> fastRemove<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>        modCount++;</li><li>        <span class="keyword">int</span> numMoved = size - index - <span class="number">1</span>;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span>numMoved <span class="bracket">></span> <span class="number">0</span><span class="bracket">)</span></li><li>            System.arraycopy<span class="bracket">(</span>elementData, index+<span class="number">1</span>, elementData, index,</li><li>                             numMoved<span class="bracket">)</span>;</li><li>        elementData<span class="bracket">[</span>--size<span class="bracket">]</span> = <span class="keyword">null</span>; <span class="comment">// clear to let GC do its work</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Removes all of the elements from this list.  The list will</span></li><li><span class="doc">     * be empty after this call returns.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">void</span> clear<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>        modCount++;</li><li></li><li>        <span class="comment">// clear to let GC do its work</span></li><li>        <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i = <span class="number">0</span>; i <span class="bracket"><</span> size; i++<span class="bracket">)</span></li><li>            elementData<span class="bracket">[</span>i<span class="bracket">]</span> = <span class="keyword">null</span>;</li><li></li><li>        size = <span class="number">0</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Appends all of the elements in the specified collection to the end of</span></li><li><span class="doc">     * this list, in the order that they are returned by the</span></li><li><span class="doc">     * specified collection's Iterator.  The behavior of this operation is</span></li><li><span class="doc">     * undefined if the specified collection is modified while the operation</span></li><li><span class="doc">     * is in progress.  (This implies that the behavior of this call is</span></li><li><span class="doc">     * undefined if the specified collection is this list, and this</span></li><li><span class="doc">     * list is nonempty.)</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param c collection containing elements to be added to this list</span></li><li><span class="doc">     * @return &lt;tt&gt;true&lt;/tt&gt; if this list changed as a result of the call</span></li><li><span class="doc">     * @throws NullPointerException if the specified collection is null</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">boolean</span> addAll<span class="bracket">(</span>Collection<span class="bracket"><</span>? <span class="keyword">extends</span> <span class="builtin_var">E</span><span class="bracket">></span> c<span class="bracket">)</span> <span class="bracket">{</span></li><li>        Object<span class="bracket">[</span><span class="bracket">]</span> a = c.toArray<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="keyword">int</span> numNew = a.length;</li><li>        ensureCapacityInternal<span class="bracket">(</span>size + numNew<span class="bracket">)</span>;  <span class="comment">// Increments modCount</span></li><li>        System.arraycopy<span class="bracket">(</span>a, <span class="number">0</span>, elementData, size, numNew<span class="bracket">)</span>;</li><li>        size += numNew;</li><li>        <span class="keyword">return</span> numNew != <span class="number">0</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Inserts all of the elements in the specified collection into this</span></li><li><span class="doc">     * list, starting at the specified position.  Shifts the element</span></li><li><span class="doc">     * currently at that position (if any) and any subsequent elements to</span></li><li><span class="doc">     * the right (increases their indices).  The new elements will appear</span></li><li><span class="doc">     * in the list in the order that they are returned by the</span></li><li><span class="doc">     * specified collection's iterator.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param index index at which to insert the first element from the</span></li><li><span class="doc">     *              specified collection</span></li><li><span class="doc">     * @param c collection containing elements to be added to this list</span></li><li><span class="doc">     * @return &lt;tt&gt;true&lt;/tt&gt; if this list changed as a result of the call</span></li><li><span class="doc">     * @throws IndexOutOfBoundsException {@inheritDoc}</span></li><li><span class="doc">     * @throws NullPointerException if the specified collection is null</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">boolean</span> addAll<span class="bracket">(</span><span class="keyword">int</span> index, Collection<span class="bracket"><</span>? <span class="keyword">extends</span> <span class="builtin_var">E</span><span class="bracket">></span> c<span class="bracket">)</span> <span class="bracket">{</span></li><li>        rangeCheckForAdd<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li></li><li>        Object<span class="bracket">[</span><span class="bracket">]</span> a = c.toArray<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="keyword">int</span> numNew = a.length;</li><li>        ensureCapacityInternal<span class="bracket">(</span>size + numNew<span class="bracket">)</span>;  <span class="comment">// Increments modCount</span></li><li></li><li>        <span class="keyword">int</span> numMoved = size - index;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span>numMoved <span class="bracket">></span> <span class="number">0</span><span class="bracket">)</span></li><li>            System.arraycopy<span class="bracket">(</span>elementData, index, elementData, index + numNew,</li><li>                             numMoved<span class="bracket">)</span>;</li><li></li><li>        System.arraycopy<span class="bracket">(</span>a, <span class="number">0</span>, elementData, index, numNew<span class="bracket">)</span>;</li><li>        size += numNew;</li><li>        <span class="keyword">return</span> numNew != <span class="number">0</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Removes from this list all of the elements whose index is between</span></li><li><span class="doc">     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.</span></li><li><span class="doc">     * Shifts any succeeding elements to the left (reduces their index).</span></li><li><span class="doc">     * This call shortens the list by {@code (toIndex - fromIndex)} elements.</span></li><li><span class="doc">     * (If {@code toIndex==fromIndex}, this operation has no effect.)</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @throws IndexOutOfBoundsException if {@code fromIndex} or</span></li><li><span class="doc">     *         {@code toIndex} is out of range</span></li><li><span class="doc">     *         ({@code fromIndex &lt; 0 ||</span></li><li><span class="doc">     *          fromIndex &gt;= size() ||</span></li><li><span class="doc">     *          toIndex &gt; size() ||</span></li><li><span class="doc">     *          toIndex &lt; fromIndex})</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">protected</span> <span class="keyword">void</span> removeRange<span class="bracket">(</span><span class="keyword">int</span> fromIndex, <span class="keyword">int</span> toIndex<span class="bracket">)</span> <span class="bracket">{</span></li><li>        modCount++;</li><li>        <span class="keyword">int</span> numMoved = size - toIndex;</li><li>        System.arraycopy<span class="bracket">(</span>elementData, toIndex, elementData, fromIndex,</li><li>                         numMoved<span class="bracket">)</span>;</li><li></li><li>        <span class="comment">// clear to let GC do its work</span></li><li>        <span class="keyword">int</span> newSize = size - <span class="bracket">(</span>toIndex-fromIndex<span class="bracket">)</span>;</li><li>        <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i = newSize; i <span class="bracket"><</span> size; i++<span class="bracket">)</span> <span class="bracket">{</span></li><li>            elementData<span class="bracket">[</span>i<span class="bracket">]</span> = <span class="keyword">null</span>;</li><li>        <span class="bracket">}</span></li><li>        size = newSize;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Checks if the given index is in range.  If not, throws an appropriate</span></li><li><span class="doc">     * runtime exception.  This method does *not* check if the index is</span></li><li><span class="doc">     * negative: It is always used immediately prior to an array access,</span></li><li><span class="doc">     * which throws an ArrayIndexOutOfBoundsException if index is negative.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">void</span> rangeCheck<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>index <span class="bracket">></span>= size<span class="bracket">)</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> IndexOutOfBoundsException<span class="bracket">(</span>outOfBoundsMsg<span class="bracket">(</span>index<span class="bracket">)</span><span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * A version of rangeCheck used by add and addAll.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">void</span> rangeCheckForAdd<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>index <span class="bracket">></span> size || index <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> IndexOutOfBoundsException<span class="bracket">(</span>outOfBoundsMsg<span class="bracket">(</span>index<span class="bracket">)</span><span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Constructs an IndexOutOfBoundsException detail message.</span></li><li><span class="doc">     * Of the many possible refactorings of the error handling code,</span></li><li><span class="doc">     * this &quot;outlining&quot; performs best with both server and client VMs.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> String outOfBoundsMsg<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">return</span> <span class="string">&quot;Index: &quot;</span>+index+<span class="string">&quot;, Size: &quot;</span>+size;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Removes from this list all of its elements that are contained in the</span></li><li><span class="doc">     * specified collection.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param c collection containing elements to be removed from this list</span></li><li><span class="doc">     * @return {@code true} if this list changed as a result of the call</span></li><li><span class="doc">     * @throws ClassCastException if the class of an element of this list</span></li><li><span class="doc">     *         is incompatible with the specified collection</span></li><li><span class="doc">     * (&lt;a href=&quot;Collection.html&#35;optional-restrictions&quot;&gt;optional&lt;/a&gt;)</span></li><li><span class="doc">     * @throws NullPointerException if this list contains a null element and the</span></li><li><span class="doc">     *         specified collection does not permit null elements</span></li><li><span class="doc">     * (&lt;a href=&quot;Collection.html&#35;optional-restrictions&quot;&gt;optional&lt;/a&gt;),</span></li><li><span class="doc">     *         or if the specified collection is null</span></li><li><span class="doc">     * @see Collection&#35;contains(Object)</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">boolean</span> removeAll<span class="bracket">(</span>Collection<span class="bracket"><</span>?<span class="bracket">></span> c<span class="bracket">)</span> <span class="bracket">{</span></li><li>        Objects.requireNonNull<span class="bracket">(</span>c<span class="bracket">)</span>;</li><li>        <span class="keyword">return</span> batchRemove<span class="bracket">(</span>c, <span class="keyword">false</span><span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Retains only the elements in this list that are contained in the</span></li><li><span class="doc">     * specified collection.  In other words, removes from this list all</span></li><li><span class="doc">     * of its elements that are not contained in the specified collection.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @param c collection containing elements to be retained in this list</span></li><li><span class="doc">     * @return {@code true} if this list changed as a result of the call</span></li><li><span class="doc">     * @throws ClassCastException if the class of an element of this list</span></li><li><span class="doc">     *         is incompatible with the specified collection</span></li><li><span class="doc">     * (&lt;a href=&quot;Collection.html&#35;optional-restrictions&quot;&gt;optional&lt;/a&gt;)</span></li><li><span class="doc">     * @throws NullPointerException if this list contains a null element and the</span></li><li><span class="doc">     *         specified collection does not permit null elements</span></li><li><span class="doc">     * (&lt;a href=&quot;Collection.html&#35;optional-restrictions&quot;&gt;optional&lt;/a&gt;),</span></li><li><span class="doc">     *         or if the specified collection is null</span></li><li><span class="doc">     * @see Collection&#35;contains(Object)</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> <span class="keyword">boolean</span> retainAll<span class="bracket">(</span>Collection<span class="bracket"><</span>?<span class="bracket">></span> c<span class="bracket">)</span> <span class="bracket">{</span></li><li>        Objects.requireNonNull<span class="bracket">(</span>c<span class="bracket">)</span>;</li><li>        <span class="keyword">return</span> batchRemove<span class="bracket">(</span>c, <span class="keyword">true</span><span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="keyword">private</span> <span class="keyword">boolean</span> batchRemove<span class="bracket">(</span>Collection<span class="bracket"><</span>?<span class="bracket">></span> c, <span class="keyword">boolean</span> complement<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">final</span> Object<span class="bracket">[</span><span class="bracket">]</span> elementData = <span class="keyword">this</span>.elementData;</li><li>        <span class="keyword">int</span> r = <span class="number">0</span>, w = <span class="number">0</span>;</li><li>        <span class="keyword">boolean</span> modified = <span class="keyword">false</span>;</li><li>        <span class="keyword">try</span> <span class="bracket">{</span></li><li>            <span class="keyword">for</span> <span class="bracket">(</span>; r <span class="bracket"><</span> size; r++<span class="bracket">)</span></li><li>                <span class="keyword">if</span> <span class="bracket">(</span>c.contains<span class="bracket">(</span>elementData<span class="bracket">[</span>r<span class="bracket">]</span><span class="bracket">)</span> == complement<span class="bracket">)</span></li><li>                    elementData<span class="bracket">[</span>w++<span class="bracket">]</span> = elementData<span class="bracket">[</span>r<span class="bracket">]</span>;</li><li>        <span class="bracket">}</span> <span class="keyword">finally</span> <span class="bracket">{</span></li><li>            <span class="comment">// Preserve behavioral compatibility with AbstractCollection,</span></li><li>            <span class="comment">// even if c.contains() throws.</span></li><li>            <span class="keyword">if</span> <span class="bracket">(</span>r != size<span class="bracket">)</span> <span class="bracket">{</span></li><li>                System.arraycopy<span class="bracket">(</span>elementData, r,</li><li>                                 elementData, w,</li><li>                                 size - r<span class="bracket">)</span>;</li><li>                w += size - r;</li><li>            <span class="bracket">}</span></li><li>            <span class="keyword">if</span> <span class="bracket">(</span>w != size<span class="bracket">)</span> <span class="bracket">{</span></li><li>                <span class="comment">// clear to let GC do its work</span></li><li>                <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i = w; i <span class="bracket"><</span> size; i++<span class="bracket">)</span></li><li>                    elementData<span class="bracket">[</span>i<span class="bracket">]</span> = <span class="keyword">null</span>;</li><li>                modCount += size - w;</li><li>                size = w;</li><li>                modified = <span class="keyword">true</span>;</li><li>            <span class="bracket">}</span></li><li>        <span class="bracket">}</span></li><li>        <span class="keyword">return</span> modified;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Save the state of the &lt;tt&gt;ArrayList&lt;/tt&gt; instance to a stream (that</span></li><li><span class="doc">     * is, serialize it).</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @serialData The length of the array backing the &lt;tt&gt;ArrayList&lt;/tt&gt;</span></li><li><span class="doc">     *             instance is emitted (int), followed by all of its elements</span></li><li><span class="doc">     *             (each an &lt;tt&gt;Object&lt;/tt&gt;) in the proper order.</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">void</span> writeObject<span class="bracket">(</span>java.io.ObjectOutputStream s<span class="bracket">)</span></li><li>        <span class="keyword">throws</span> java.io.IOException<span class="bracket">{</span></li><li>        <span class="comment">// Write out element count, and any hidden stuff</span></li><li>        <span class="keyword">int</span> expectedModCount = modCount;</li><li>        s.defaultWriteObject<span class="bracket">(</span><span class="bracket">)</span>;</li><li></li><li>        <span class="comment">// Write out size as capacity for behavioural compatibility with clone()</span></li><li>        s.writeInt<span class="bracket">(</span>size<span class="bracket">)</span>;</li><li></li><li>        <span class="comment">// Write out all elements in the proper order.</span></li><li>        <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i=<span class="number">0</span>; i<span class="bracket"><</span>size; i++<span class="bracket">)</span> <span class="bracket">{</span></li><li>            s.writeObject<span class="bracket">(</span>elementData<span class="bracket">[</span>i<span class="bracket">]</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>modCount != expectedModCount<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Reconstitute the &lt;tt&gt;ArrayList&lt;/tt&gt; instance from a stream (that is,</span></li><li><span class="doc">     * deserialize it).</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">void</span> readObject<span class="bracket">(</span>java.io.ObjectInputStream s<span class="bracket">)</span></li><li>        <span class="keyword">throws</span> java.io.IOException, ClassNotFoundException <span class="bracket">{</span></li><li>        elementData = EMPTY_ELEMENTDATA;</li><li></li><li>        <span class="comment">// Read in size, and any hidden stuff</span></li><li>        s.defaultReadObject<span class="bracket">(</span><span class="bracket">)</span>;</li><li></li><li>        <span class="comment">// Read in capacity</span></li><li>        s.readInt<span class="bracket">(</span><span class="bracket">)</span>; <span class="comment">// ignored</span></li><li></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>size <span class="bracket">></span> <span class="number">0</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="comment">// be like clone(), allocate array based upon size not capacity</span></li><li>            <span class="keyword">int</span> capacity = calculateCapacity<span class="bracket">(</span>elementData, size<span class="bracket">)</span>;</li><li>            SharedSecrets.getJavaOISAccess<span class="bracket">(</span><span class="bracket">)</span>.checkArray<span class="bracket">(</span>s, Object<span class="bracket">[</span><span class="bracket">]</span>.<span class="keyword">class</span>, capacity<span class="bracket">)</span>;</li><li>            ensureCapacityInternal<span class="bracket">(</span>size<span class="bracket">)</span>;</li><li></li><li>            Object<span class="bracket">[</span><span class="bracket">]</span> a = elementData;</li><li>            <span class="comment">// Read in all elements in the proper order.</span></li><li>            <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i=<span class="number">0</span>; i<span class="bracket"><</span>size; i++<span class="bracket">)</span> <span class="bracket">{</span></li><li>                a<span class="bracket">[</span>i<span class="bracket">]</span> = s.readObject<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="bracket">}</span></li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns a list iterator over the elements in this list (in proper</span></li><li><span class="doc">     * sequence), starting at the specified position in the list.</span></li><li><span class="doc">     * The specified index indicates the first element that would be</span></li><li><span class="doc">     * returned by an initial call to {@link ListIterator&#35;next next}.</span></li><li><span class="doc">     * An initial call to {@link ListIterator&#35;previous previous} would</span></li><li><span class="doc">     * return the element with the specified index minus one.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * &lt;p&gt;The returned list iterator is &lt;a href=&quot;&#35;fail-fast&quot;&gt;&lt;i&gt;fail-fast&lt;/i&gt;&lt;/a&gt;.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @throws IndexOutOfBoundsException {@inheritDoc}</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> ListIterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> listIterator<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>index <span class="bracket"><</span> <span class="number">0</span> || index <span class="bracket">></span> size<span class="bracket">)</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> IndexOutOfBoundsException<span class="bracket">(</span><span class="string">&quot;Index: &quot;</span>+index<span class="bracket">)</span>;</li><li>        <span class="keyword">return</span> <span class="keyword">new</span> ListItr<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns a list iterator over the elements in this list (in proper</span></li><li><span class="doc">     * sequence).</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * &lt;p&gt;The returned list iterator is &lt;a href=&quot;&#35;fail-fast&quot;&gt;&lt;i&gt;fail-fast&lt;/i&gt;&lt;/a&gt;.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @see &#35;listIterator(int)</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> ListIterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> listIterator<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">return</span> <span class="keyword">new</span> ListItr<span class="bracket">(</span><span class="number">0</span><span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns an iterator over the elements in this list in proper sequence.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * &lt;p&gt;The returned iterator is &lt;a href=&quot;&#35;fail-fast&quot;&gt;&lt;i&gt;fail-fast&lt;/i&gt;&lt;/a&gt;.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @return an iterator over the elements in this list in proper sequence</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> Iterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> iterator<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">return</span> <span class="keyword">new</span> Itr<span class="bracket">(</span><span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * An optimized version of AbstractList.Itr</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">class</span> Itr <span class="keyword">implements</span> Iterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> <span class="bracket">{</span></li><li>        <span class="keyword">int</span> cursor;       <span class="comment">// index of next element to return</span></li><li>        <span class="keyword">int</span> lastRet = -<span class="number">1</span>; <span class="comment">// index of last element returned; -1 if no such</span></li><li>        <span class="keyword">int</span> expectedModCount = modCount;</li><li></li><li>        Itr<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span><span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">boolean</span> hasNext<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">return</span> cursor != size;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>        <span class="keyword">public</span> <span class="builtin_var">E</span> next<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="keyword">int</span> i = cursor;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span>i <span class="bracket">></span>= size<span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            Object<span class="bracket">[</span><span class="bracket">]</span> elementData = ArrayList.<span class="keyword">this</span>.elementData;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span>i <span class="bracket">></span>= elementData.length<span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            cursor = i + <span class="number">1</span>;</li><li>            <span class="keyword">return</span> <span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">)</span> elementData<span class="bracket">[</span>lastRet = i<span class="bracket">]</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">void</span> remove<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">if</span> <span class="bracket">(</span>lastRet <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> IllegalStateException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li></li><li>            <span class="keyword">try</span> <span class="bracket">{</span></li><li>                ArrayList.<span class="keyword">this</span>.remove<span class="bracket">(</span>lastRet<span class="bracket">)</span>;</li><li>                cursor = lastRet;</li><li>                lastRet = -<span class="number">1</span>;</li><li>                expectedModCount = modCount;</li><li>            <span class="bracket">}</span> <span class="keyword">catch</span> <span class="bracket">(</span>IndexOutOfBoundsException ex<span class="bracket">)</span> <span class="bracket">{</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="bracket">}</span></li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="description">@Override</span></li><li>        <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>        <span class="keyword">public</span> <span class="keyword">void</span> forEachRemaining<span class="bracket">(</span>Consumer<span class="bracket"><</span>? <span class="keyword">super</span> <span class="builtin_var">E</span><span class="bracket">></span> consumer<span class="bracket">)</span> <span class="bracket">{</span></li><li>            Objects.requireNonNull<span class="bracket">(</span>consumer<span class="bracket">)</span>;</li><li>            <span class="keyword">final</span> <span class="keyword">int</span> size = ArrayList.<span class="keyword">this</span>.size;</li><li>            <span class="keyword">int</span> i = cursor;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span>i <span class="bracket">></span>= size<span class="bracket">)</span> <span class="bracket">{</span></li><li>                <span class="keyword">return</span>;</li><li>            <span class="bracket">}</span></li><li>            <span class="keyword">final</span> Object<span class="bracket">[</span><span class="bracket">]</span> elementData = ArrayList.<span class="keyword">this</span>.elementData;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span>i <span class="bracket">></span>= elementData.length<span class="bracket">)</span> <span class="bracket">{</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="bracket">}</span></li><li>            <span class="keyword">while</span> <span class="bracket">(</span>i != size && modCount == expectedModCount<span class="bracket">)</span> <span class="bracket">{</span></li><li>                consumer.accept<span class="bracket">(</span><span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">)</span> elementData<span class="bracket">[</span>i++<span class="bracket">]</span><span class="bracket">)</span>;</li><li>            <span class="bracket">}</span></li><li>            <span class="comment">// update once at end of iteration to reduce heap write traffic</span></li><li>            cursor = i;</li><li>            lastRet = i - <span class="number">1</span>;</li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">final</span> <span class="keyword">void</span> checkForComodification<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">if</span> <span class="bracket">(</span>modCount != expectedModCount<span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * An optimized version of AbstractList.ListItr</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">private</span> <span class="keyword">class</span> ListItr <span class="keyword">extends</span> Itr <span class="keyword">implements</span> ListIterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> <span class="bracket">{</span></li><li>        ListItr<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">super</span><span class="bracket">(</span><span class="bracket">)</span>;</li><li>            cursor = index;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">boolean</span> hasPrevious<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">return</span> cursor != <span class="number">0</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">int</span> nextIndex<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">return</span> cursor;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">int</span> previousIndex<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">return</span> cursor - <span class="number">1</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>        <span class="keyword">public</span> <span class="builtin_var">E</span> previous<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="keyword">int</span> i = cursor - <span class="number">1</span>;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span>i <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            Object<span class="bracket">[</span><span class="bracket">]</span> elementData = ArrayList.<span class="keyword">this</span>.elementData;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span>i <span class="bracket">></span>= elementData.length<span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            cursor = i;</li><li>            <span class="keyword">return</span> <span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">)</span> elementData<span class="bracket">[</span>lastRet = i<span class="bracket">]</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">void</span> set<span class="bracket">(</span><span class="builtin_var">E</span> e<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">if</span> <span class="bracket">(</span>lastRet <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> IllegalStateException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li></li><li>            <span class="keyword">try</span> <span class="bracket">{</span></li><li>                ArrayList.<span class="keyword">this</span>.set<span class="bracket">(</span>lastRet, e<span class="bracket">)</span>;</li><li>            <span class="bracket">}</span> <span class="keyword">catch</span> <span class="bracket">(</span>IndexOutOfBoundsException ex<span class="bracket">)</span> <span class="bracket">{</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="bracket">}</span></li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">void</span> add<span class="bracket">(</span><span class="builtin_var">E</span> e<span class="bracket">)</span> <span class="bracket">{</span></li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li></li><li>            <span class="keyword">try</span> <span class="bracket">{</span></li><li>                <span class="keyword">int</span> i = cursor;</li><li>                ArrayList.<span class="keyword">this</span>.add<span class="bracket">(</span>i, e<span class="bracket">)</span>;</li><li>                cursor = i + <span class="number">1</span>;</li><li>                lastRet = -<span class="number">1</span>;</li><li>                expectedModCount = modCount;</li><li>            <span class="bracket">}</span> <span class="keyword">catch</span> <span class="bracket">(</span>IndexOutOfBoundsException ex<span class="bracket">)</span> <span class="bracket">{</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="bracket">}</span></li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Returns a view of the portion of this list between the specified</span></li><li><span class="doc">     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If</span></li><li><span class="doc">     * {@code fromIndex} and {@code toIndex} are equal, the returned list is</span></li><li><span class="doc">     * empty.)  The returned list is backed by this list, so non-structural</span></li><li><span class="doc">     * changes in the returned list are reflected in this list, and vice-versa.</span></li><li><span class="doc">     * The returned list supports all of the optional list operations.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * &lt;p&gt;This method eliminates the need for explicit range operations (of</span></li><li><span class="doc">     * the sort that commonly exist for arrays).  Any operation that expects</span></li><li><span class="doc">     * a list can be used as a range operation by passing a subList view</span></li><li><span class="doc">     * instead of a whole list.  For example, the following idiom</span></li><li><span class="doc">     * removes a range of elements from a list:</span></li><li><span class="doc">     * &lt;pre&gt;</span></li><li><span class="doc">     *      list.subList(from, to).clear();</span></li><li><span class="doc">     * &lt;/pre&gt;</span></li><li><span class="doc">     * Similar idioms may be constructed for {@link &#35;indexOf(Object)} and</span></li><li><span class="doc">     * {@link &#35;lastIndexOf(Object)}, and all of the algorithms in the</span></li><li><span class="doc">     * {@link Collections} class can be applied to a subList.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * &lt;p&gt;The semantics of the list returned by this method become undefined if</span></li><li><span class="doc">     * the backing list (i.e., this list) is &lt;i&gt;structurally modified&lt;/i&gt; in</span></li><li><span class="doc">     * any way other than via the returned list.  (Structural modifications are</span></li><li><span class="doc">     * those that change the size of this list, or otherwise perturb it in such</span></li><li><span class="doc">     * a fashion that iterations in progress may yield incorrect results.)</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @throws IndexOutOfBoundsException {@inheritDoc}</span></li><li><span class="doc">     * @throws IllegalArgumentException {@inheritDoc}</span></li><li><span class="doc">     */</span></li><li>    <span class="keyword">public</span> List<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> subList<span class="bracket">(</span><span class="keyword">int</span> fromIndex, <span class="keyword">int</span> toIndex<span class="bracket">)</span> <span class="bracket">{</span></li><li>        subListRangeCheck<span class="bracket">(</span>fromIndex, toIndex, size<span class="bracket">)</span>;</li><li>        <span class="keyword">return</span> <span class="keyword">new</span> SubList<span class="bracket">(</span><span class="keyword">this</span>, <span class="number">0</span>, fromIndex, toIndex<span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="keyword">static</span> <span class="keyword">void</span> subListRangeCheck<span class="bracket">(</span><span class="keyword">int</span> fromIndex, <span class="keyword">int</span> toIndex, <span class="keyword">int</span> size<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>fromIndex <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> IndexOutOfBoundsException<span class="bracket">(</span><span class="string">&quot;fromIndex = &quot;</span> + fromIndex<span class="bracket">)</span>;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span>toIndex <span class="bracket">></span> size<span class="bracket">)</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> IndexOutOfBoundsException<span class="bracket">(</span><span class="string">&quot;toIndex = &quot;</span> + toIndex<span class="bracket">)</span>;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span>fromIndex <span class="bracket">></span> toIndex<span class="bracket">)</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException<span class="bracket">(</span><span class="string">&quot;fromIndex(&quot;</span> + fromIndex +</li><li>                                               <span class="string">&quot;) &gt; toIndex(&quot;</span> + toIndex + <span class="string">&quot;)&quot;</span><span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="keyword">private</span> <span class="keyword">class</span> SubList <span class="keyword">extends</span> AbstractList<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> <span class="keyword">implements</span> RandomAccess <span class="bracket">{</span></li><li>        <span class="keyword">private</span> <span class="keyword">final</span> AbstractList<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> parent;</li><li>        <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">int</span> parentOffset;</li><li>        <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">int</span> offset;</li><li>        <span class="keyword">int</span> size;</li><li></li><li>        SubList<span class="bracket">(</span>AbstractList<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> parent,</li><li>                <span class="keyword">int</span> offset, <span class="keyword">int</span> fromIndex, <span class="keyword">int</span> toIndex<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">this</span>.parent = parent;</li><li>            <span class="keyword">this</span>.parentOffset = fromIndex;</li><li>            <span class="keyword">this</span>.offset = offset + fromIndex;</li><li>            <span class="keyword">this</span>.size = toIndex - fromIndex;</li><li>            <span class="keyword">this</span>.modCount = ArrayList.<span class="keyword">this</span>.modCount;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="builtin_var">E</span> set<span class="bracket">(</span><span class="keyword">int</span> index, <span class="builtin_var">E</span> e<span class="bracket">)</span> <span class="bracket">{</span></li><li>            rangeCheck<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="builtin_var">E</span> oldValue = ArrayList.<span class="keyword">this</span>.elementData<span class="bracket">(</span>offset + index<span class="bracket">)</span>;</li><li>            ArrayList.<span class="keyword">this</span>.elementData<span class="bracket">[</span>offset + index<span class="bracket">]</span> = e;</li><li>            <span class="keyword">return</span> oldValue;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="builtin_var">E</span> get<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>            rangeCheck<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="keyword">return</span> ArrayList.<span class="keyword">this</span>.elementData<span class="bracket">(</span>offset + index<span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">int</span> size<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="keyword">return</span> <span class="keyword">this</span>.size;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">void</span> add<span class="bracket">(</span><span class="keyword">int</span> index, <span class="builtin_var">E</span> e<span class="bracket">)</span> <span class="bracket">{</span></li><li>            rangeCheckForAdd<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            parent.add<span class="bracket">(</span>parentOffset + index, e<span class="bracket">)</span>;</li><li>            <span class="keyword">this</span>.modCount = parent.modCount;</li><li>            <span class="keyword">this</span>.size++;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="builtin_var">E</span> remove<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>            rangeCheck<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="builtin_var">E</span> result = parent.remove<span class="bracket">(</span>parentOffset + index<span class="bracket">)</span>;</li><li>            <span class="keyword">this</span>.modCount = parent.modCount;</li><li>            <span class="keyword">this</span>.size--;</li><li>            <span class="keyword">return</span> result;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">protected</span> <span class="keyword">void</span> removeRange<span class="bracket">(</span><span class="keyword">int</span> fromIndex, <span class="keyword">int</span> toIndex<span class="bracket">)</span> <span class="bracket">{</span></li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            parent.removeRange<span class="bracket">(</span>parentOffset + fromIndex,</li><li>                               parentOffset + toIndex<span class="bracket">)</span>;</li><li>            <span class="keyword">this</span>.modCount = parent.modCount;</li><li>            <span class="keyword">this</span>.size -= toIndex - fromIndex;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">boolean</span> addAll<span class="bracket">(</span>Collection<span class="bracket"><</span>? <span class="keyword">extends</span> <span class="builtin_var">E</span><span class="bracket">></span> c<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">return</span> addAll<span class="bracket">(</span><span class="keyword">this</span>.size, c<span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">boolean</span> addAll<span class="bracket">(</span><span class="keyword">int</span> index, Collection<span class="bracket"><</span>? <span class="keyword">extends</span> <span class="builtin_var">E</span><span class="bracket">></span> c<span class="bracket">)</span> <span class="bracket">{</span></li><li>            rangeCheckForAdd<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li>            <span class="keyword">int</span> cSize = c.size<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span>cSize==<span class="number">0</span><span class="bracket">)</span></li><li>                <span class="keyword">return</span> <span class="keyword">false</span>;</li><li></li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            parent.addAll<span class="bracket">(</span>parentOffset + index, c<span class="bracket">)</span>;</li><li>            <span class="keyword">this</span>.modCount = parent.modCount;</li><li>            <span class="keyword">this</span>.size += cSize;</li><li>            <span class="keyword">return</span> <span class="keyword">true</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> Iterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> iterator<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">return</span> listIterator<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> ListIterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> listIterator<span class="bracket">(</span><span class="keyword">final</span> <span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            rangeCheckForAdd<span class="bracket">(</span>index<span class="bracket">)</span>;</li><li>            <span class="keyword">final</span> <span class="keyword">int</span> offset = <span class="keyword">this</span>.offset;</li><li></li><li>            <span class="keyword">return</span> <span class="keyword">new</span> ListIterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span><span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                <span class="keyword">int</span> cursor = index;</li><li>                <span class="keyword">int</span> lastRet = -<span class="number">1</span>;</li><li>                <span class="keyword">int</span> expectedModCount = ArrayList.<span class="keyword">this</span>.modCount;</li><li></li><li>                <span class="keyword">public</span> <span class="keyword">boolean</span> hasNext<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                    <span class="keyword">return</span> cursor != SubList.<span class="keyword">this</span>.size;</li><li>                <span class="bracket">}</span></li><li></li><li>                <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>                <span class="keyword">public</span> <span class="builtin_var">E</span> next<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                    checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    <span class="keyword">int</span> i = cursor;</li><li>                    <span class="keyword">if</span> <span class="bracket">(</span>i <span class="bracket">></span>= SubList.<span class="keyword">this</span>.size<span class="bracket">)</span></li><li>                        <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    Object<span class="bracket">[</span><span class="bracket">]</span> elementData = ArrayList.<span class="keyword">this</span>.elementData;</li><li>                    <span class="keyword">if</span> <span class="bracket">(</span>offset + i <span class="bracket">></span>= elementData.length<span class="bracket">)</span></li><li>                        <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    cursor = i + <span class="number">1</span>;</li><li>                    <span class="keyword">return</span> <span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">)</span> elementData<span class="bracket">[</span>offset + <span class="bracket">(</span>lastRet = i<span class="bracket">)</span><span class="bracket">]</span>;</li><li>                <span class="bracket">}</span></li><li></li><li>                <span class="keyword">public</span> <span class="keyword">boolean</span> hasPrevious<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                    <span class="keyword">return</span> cursor != <span class="number">0</span>;</li><li>                <span class="bracket">}</span></li><li></li><li>                <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>                <span class="keyword">public</span> <span class="builtin_var">E</span> previous<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                    checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    <span class="keyword">int</span> i = cursor - <span class="number">1</span>;</li><li>                    <span class="keyword">if</span> <span class="bracket">(</span>i <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span></li><li>                        <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    Object<span class="bracket">[</span><span class="bracket">]</span> elementData = ArrayList.<span class="keyword">this</span>.elementData;</li><li>                    <span class="keyword">if</span> <span class="bracket">(</span>offset + i <span class="bracket">></span>= elementData.length<span class="bracket">)</span></li><li>                        <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    cursor = i;</li><li>                    <span class="keyword">return</span> <span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">)</span> elementData<span class="bracket">[</span>offset + <span class="bracket">(</span>lastRet = i<span class="bracket">)</span><span class="bracket">]</span>;</li><li>                <span class="bracket">}</span></li><li></li><li>                <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>                <span class="keyword">public</span> <span class="keyword">void</span> forEachRemaining<span class="bracket">(</span>Consumer<span class="bracket"><</span>? <span class="keyword">super</span> <span class="builtin_var">E</span><span class="bracket">></span> consumer<span class="bracket">)</span> <span class="bracket">{</span></li><li>                    Objects.requireNonNull<span class="bracket">(</span>consumer<span class="bracket">)</span>;</li><li>                    <span class="keyword">final</span> <span class="keyword">int</span> size = SubList.<span class="keyword">this</span>.size;</li><li>                    <span class="keyword">int</span> i = cursor;</li><li>                    <span class="keyword">if</span> <span class="bracket">(</span>i <span class="bracket">></span>= size<span class="bracket">)</span> <span class="bracket">{</span></li><li>                        <span class="keyword">return</span>;</li><li>                    <span class="bracket">}</span></li><li>                    <span class="keyword">final</span> Object<span class="bracket">[</span><span class="bracket">]</span> elementData = ArrayList.<span class="keyword">this</span>.elementData;</li><li>                    <span class="keyword">if</span> <span class="bracket">(</span>offset + i <span class="bracket">></span>= elementData.length<span class="bracket">)</span> <span class="bracket">{</span></li><li>                        <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    <span class="bracket">}</span></li><li>                    <span class="keyword">while</span> <span class="bracket">(</span>i != size && modCount == expectedModCount<span class="bracket">)</span> <span class="bracket">{</span></li><li>                        consumer.accept<span class="bracket">(</span><span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">)</span> elementData<span class="bracket">[</span>offset + <span class="bracket">(</span>i++<span class="bracket">)</span><span class="bracket">]</span><span class="bracket">)</span>;</li><li>                    <span class="bracket">}</span></li><li>                    <span class="comment">// update once at end of iteration to reduce heap write traffic</span></li><li>                    lastRet = cursor = i;</li><li>                    checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                <span class="bracket">}</span></li><li></li><li>                <span class="keyword">public</span> <span class="keyword">int</span> nextIndex<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                    <span class="keyword">return</span> cursor;</li><li>                <span class="bracket">}</span></li><li></li><li>                <span class="keyword">public</span> <span class="keyword">int</span> previousIndex<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                    <span class="keyword">return</span> cursor - <span class="number">1</span>;</li><li>                <span class="bracket">}</span></li><li></li><li>                <span class="keyword">public</span> <span class="keyword">void</span> remove<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                    <span class="keyword">if</span> <span class="bracket">(</span>lastRet <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span></li><li>                        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalStateException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li></li><li>                    <span class="keyword">try</span> <span class="bracket">{</span></li><li>                        SubList.<span class="keyword">this</span>.remove<span class="bracket">(</span>lastRet<span class="bracket">)</span>;</li><li>                        cursor = lastRet;</li><li>                        lastRet = -<span class="number">1</span>;</li><li>                        expectedModCount = ArrayList.<span class="keyword">this</span>.modCount;</li><li>                    <span class="bracket">}</span> <span class="keyword">catch</span> <span class="bracket">(</span>IndexOutOfBoundsException ex<span class="bracket">)</span> <span class="bracket">{</span></li><li>                        <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    <span class="bracket">}</span></li><li>                <span class="bracket">}</span></li><li></li><li>                <span class="keyword">public</span> <span class="keyword">void</span> set<span class="bracket">(</span><span class="builtin_var">E</span> e<span class="bracket">)</span> <span class="bracket">{</span></li><li>                    <span class="keyword">if</span> <span class="bracket">(</span>lastRet <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span></li><li>                        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalStateException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li></li><li>                    <span class="keyword">try</span> <span class="bracket">{</span></li><li>                        ArrayList.<span class="keyword">this</span>.set<span class="bracket">(</span>offset + lastRet, e<span class="bracket">)</span>;</li><li>                    <span class="bracket">}</span> <span class="keyword">catch</span> <span class="bracket">(</span>IndexOutOfBoundsException ex<span class="bracket">)</span> <span class="bracket">{</span></li><li>                        <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    <span class="bracket">}</span></li><li>                <span class="bracket">}</span></li><li></li><li>                <span class="keyword">public</span> <span class="keyword">void</span> add<span class="bracket">(</span><span class="builtin_var">E</span> e<span class="bracket">)</span> <span class="bracket">{</span></li><li>                    checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li></li><li>                    <span class="keyword">try</span> <span class="bracket">{</span></li><li>                        <span class="keyword">int</span> i = cursor;</li><li>                        SubList.<span class="keyword">this</span>.add<span class="bracket">(</span>i, e<span class="bracket">)</span>;</li><li>                        cursor = i + <span class="number">1</span>;</li><li>                        lastRet = -<span class="number">1</span>;</li><li>                        expectedModCount = ArrayList.<span class="keyword">this</span>.modCount;</li><li>                    <span class="bracket">}</span> <span class="keyword">catch</span> <span class="bracket">(</span>IndexOutOfBoundsException ex<span class="bracket">)</span> <span class="bracket">{</span></li><li>                        <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                    <span class="bracket">}</span></li><li>                <span class="bracket">}</span></li><li></li><li>                <span class="keyword">final</span> <span class="keyword">void</span> checkForComodification<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                    <span class="keyword">if</span> <span class="bracket">(</span>expectedModCount != ArrayList.<span class="keyword">this</span>.modCount<span class="bracket">)</span></li><li>                        <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                <span class="bracket">}</span></li><li>            <span class="bracket">}</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> List<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> subList<span class="bracket">(</span><span class="keyword">int</span> fromIndex, <span class="keyword">int</span> toIndex<span class="bracket">)</span> <span class="bracket">{</span></li><li>            subListRangeCheck<span class="bracket">(</span>fromIndex, toIndex, size<span class="bracket">)</span>;</li><li>            <span class="keyword">return</span> <span class="keyword">new</span> SubList<span class="bracket">(</span><span class="keyword">this</span>, offset, fromIndex, toIndex<span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">private</span> <span class="keyword">void</span> rangeCheck<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">if</span> <span class="bracket">(</span>index <span class="bracket"><</span> <span class="number">0</span> || index <span class="bracket">></span>= <span class="keyword">this</span>.size<span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> IndexOutOfBoundsException<span class="bracket">(</span>outOfBoundsMsg<span class="bracket">(</span>index<span class="bracket">)</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">private</span> <span class="keyword">void</span> rangeCheckForAdd<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">if</span> <span class="bracket">(</span>index <span class="bracket"><</span> <span class="number">0</span> || index <span class="bracket">></span> <span class="keyword">this</span>.size<span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> IndexOutOfBoundsException<span class="bracket">(</span>outOfBoundsMsg<span class="bracket">(</span>index<span class="bracket">)</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">private</span> String outOfBoundsMsg<span class="bracket">(</span><span class="keyword">int</span> index<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">return</span> <span class="string">&quot;Index: &quot;</span>+index+<span class="string">&quot;, Size: &quot;</span>+<span class="keyword">this</span>.size;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">private</span> <span class="keyword">void</span> checkForComodification<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">if</span> <span class="bracket">(</span>ArrayList.<span class="keyword">this</span>.modCount != <span class="keyword">this</span>.modCount<span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> Spliterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> spliterator<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            checkForComodification<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="keyword">return</span> <span class="keyword">new</span> ArrayListSpliterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span><span class="bracket">(</span>ArrayList.<span class="keyword">this</span>, offset,</li><li>                                               offset + <span class="keyword">this</span>.size, <span class="keyword">this</span>.modCount<span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="description">@Override</span></li><li>    <span class="keyword">public</span> <span class="keyword">void</span> forEach<span class="bracket">(</span>Consumer<span class="bracket"><</span>? <span class="keyword">super</span> <span class="builtin_var">E</span><span class="bracket">></span> action<span class="bracket">)</span> <span class="bracket">{</span></li><li>        Objects.requireNonNull<span class="bracket">(</span>action<span class="bracket">)</span>;</li><li>        <span class="keyword">final</span> <span class="keyword">int</span> expectedModCount = modCount;</li><li>        <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>        <span class="keyword">final</span> <span class="builtin_var">E</span><span class="bracket">[</span><span class="bracket">]</span> elementData = <span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">[</span><span class="bracket">]</span><span class="bracket">)</span> <span class="keyword">this</span>.elementData;</li><li>        <span class="keyword">final</span> <span class="keyword">int</span> size = <span class="keyword">this</span>.size;</li><li>        <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i=<span class="number">0</span>; modCount == expectedModCount && i <span class="bracket"><</span> size; i++<span class="bracket">)</span> <span class="bracket">{</span></li><li>            action.accept<span class="bracket">(</span>elementData<span class="bracket">[</span>i<span class="bracket">]</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>modCount != expectedModCount<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/**</span></li><li><span class="doc">     * Creates a &lt;em&gt;&lt;a href=&quot;Spliterator.html&#35;binding&quot;&gt;late-binding&lt;/a&gt;&lt;/em&gt;</span></li><li><span class="doc">     * and &lt;em&gt;fail-fast&lt;/em&gt; {@link Spliterator} over the elements in this</span></li><li><span class="doc">     * list.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * &lt;p&gt;The {@code Spliterator} reports {@link Spliterator&#35;SIZED},</span></li><li><span class="doc">     * {@link Spliterator&#35;SUBSIZED}, and {@link Spliterator&#35;ORDERED}.</span></li><li><span class="doc">     * Overriding implementations should document the reporting of additional</span></li><li><span class="doc">     * characteristic values.</span></li><li><span class="doc">     *</span></li><li><span class="doc">     * @return a {@code Spliterator} over the elements in this list</span></li><li><span class="doc">     * @since 1.8</span></li><li><span class="doc">     */</span></li><li>    <span class="description">@Override</span></li><li>    <span class="keyword">public</span> Spliterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> spliterator<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">return</span> <span class="keyword">new</span> ArrayListSpliterator<span class="bracket"><</span><span class="bracket">></span><span class="bracket">(</span><span class="keyword">this</span>, <span class="number">0</span>, -<span class="number">1</span>, <span class="number">0</span><span class="bracket">)</span>;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="doc">/** Index-based split-by-two, lazily initialized Spliterator */</span></li><li>    <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">class</span> ArrayListSpliterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> <span class="keyword">implements</span> Spliterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> <span class="bracket">{</span></li><li></li><li>        <span class="comment">/*</span></li><li><span class="comment">         * If ArrayLists were immutable, or structurally immutable (no</span></li><li><span class="comment">         * adds, removes, etc), we could implement their spliterators</span></li><li><span class="comment">         * with Arrays.spliterator. Instead we detect as much</span></li><li><span class="comment">         * interference during traversal as practical without</span></li><li><span class="comment">         * sacrificing much performance. We rely primarily on</span></li><li><span class="comment">         * modCounts. These are not guaranteed to detect concurrency</span></li><li><span class="comment">         * violations, and are sometimes overly conservative about</span></li><li><span class="comment">         * within-thread interference, but detect enough problems to</span></li><li><span class="comment">         * be worthwhile in practice. To carry this out, we (1) lazily</span></li><li><span class="comment">         * initialize fence and expectedModCount until the latest</span></li><li><span class="comment">         * point that we need to commit to the state we are checking</span></li><li><span class="comment">         * against; thus improving precision.  (This doesn't apply to</span></li><li><span class="comment">         * SubLists, that create spliterators with current non-lazy</span></li><li><span class="comment">         * values).  (2) We perform only a single</span></li><li><span class="comment">         * ConcurrentModificationException check at the end of forEach</span></li><li><span class="comment">         * (the most performance-sensitive method). When using forEach</span></li><li><span class="comment">         * (as opposed to iterators), we can normally only detect</span></li><li><span class="comment">         * interference after actions, not before. Further</span></li><li><span class="comment">         * CME-triggering checks apply to all other possible</span></li><li><span class="comment">         * violations of assumptions for example null or too-small</span></li><li><span class="comment">         * elementData array given its size(), that could only have</span></li><li><span class="comment">         * occurred due to interference.  This allows the inner loop</span></li><li><span class="comment">         * of forEach to run without any further checks, and</span></li><li><span class="comment">         * simplifies lambda-resolution. While this does entail a</span></li><li><span class="comment">         * number of checks, note that in the common case of</span></li><li><span class="comment">         * list.stream().forEach(a), no checks or other computation</span></li><li><span class="comment">         * occur anywhere other than inside forEach itself.  The other</span></li><li><span class="comment">         * less-often-used methods cannot take advantage of most of</span></li><li><span class="comment">         * these streamlinings.</span></li><li><span class="comment">         */</span></li><li></li><li>        <span class="keyword">private</span> <span class="keyword">final</span> ArrayList<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> list;</li><li>        <span class="keyword">private</span> <span class="keyword">int</span> index; <span class="comment">// current index, modified on advance/split</span></li><li>        <span class="keyword">private</span> <span class="keyword">int</span> fence; <span class="comment">// -1 until used; then one past last index</span></li><li>        <span class="keyword">private</span> <span class="keyword">int</span> expectedModCount; <span class="comment">// initialized when fence set</span></li><li></li><li>        <span class="doc">/** Create new spliterator covering the given  range */</span></li><li>        ArrayListSpliterator<span class="bracket">(</span>ArrayList<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> list, <span class="keyword">int</span> origin, <span class="keyword">int</span> fence,</li><li>                             <span class="keyword">int</span> expectedModCount<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">this</span>.list = list; <span class="comment">// OK if null unless traversed</span></li><li>            <span class="keyword">this</span>.index = origin;</li><li>            <span class="keyword">this</span>.fence = fence;</li><li>            <span class="keyword">this</span>.expectedModCount = expectedModCount;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">private</span> <span class="keyword">int</span> getFence<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span> <span class="comment">// initialize fence to size on first use</span></li><li>            <span class="keyword">int</span> hi; <span class="comment">// (a specialized variant appears in method forEach)</span></li><li>            ArrayList<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> lst;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span><span class="bracket">(</span>hi = fence<span class="bracket">)</span> <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                <span class="keyword">if</span> <span class="bracket">(</span><span class="bracket">(</span>lst = list<span class="bracket">)</span> == <span class="keyword">null</span><span class="bracket">)</span></li><li>                    hi = fence = <span class="number">0</span>;</li><li>                <span class="keyword">else</span> <span class="bracket">{</span></li><li>                    expectedModCount = lst.modCount;</li><li>                    hi = fence = lst.size;</li><li>                <span class="bracket">}</span></li><li>            <span class="bracket">}</span></li><li>            <span class="keyword">return</span> hi;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> ArrayListSpliterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> trySplit<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">int</span> hi = getFence<span class="bracket">(</span><span class="bracket">)</span>, lo = index, mid = <span class="bracket">(</span>lo + hi<span class="bracket">)</span> <span class="bracket">></span><span class="bracket">></span><span class="bracket">></span> <span class="number">1</span>;</li><li>            <span class="keyword">return</span> <span class="bracket">(</span>lo <span class="bracket">></span>= mid<span class="bracket">)</span> ? <span class="keyword">null</span> : <span class="comment">// divide range in half unless too small</span></li><li>                <span class="keyword">new</span> ArrayListSpliterator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span><span class="bracket">(</span>list, lo, index = mid,</li><li>                                            expectedModCount<span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">boolean</span> tryAdvance<span class="bracket">(</span>Consumer<span class="bracket"><</span>? <span class="keyword">super</span> <span class="builtin_var">E</span><span class="bracket">></span> action<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">if</span> <span class="bracket">(</span>action == <span class="keyword">null</span><span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="keyword">int</span> hi = getFence<span class="bracket">(</span><span class="bracket">)</span>, i = index;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span>i <span class="bracket"><</span> hi<span class="bracket">)</span> <span class="bracket">{</span></li><li>                index = i + <span class="number">1</span>;</li><li>                <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span> <span class="builtin_var">E</span> e = <span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">)</span>list.elementData<span class="bracket">[</span>i<span class="bracket">]</span>;</li><li>                action.accept<span class="bracket">(</span>e<span class="bracket">)</span>;</li><li>                <span class="keyword">if</span> <span class="bracket">(</span>list.modCount != expectedModCount<span class="bracket">)</span></li><li>                    <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>                <span class="keyword">return</span> <span class="keyword">true</span>;</li><li>            <span class="bracket">}</span></li><li>            <span class="keyword">return</span> <span class="keyword">false</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">void</span> forEachRemaining<span class="bracket">(</span>Consumer<span class="bracket"><</span>? <span class="keyword">super</span> <span class="builtin_var">E</span><span class="bracket">></span> action<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">int</span> i, hi, mc; <span class="comment">// hoist accesses and checks from loop</span></li><li>            ArrayList<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> lst; Object<span class="bracket">[</span><span class="bracket">]</span> a;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span>action == <span class="keyword">null</span><span class="bracket">)</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span><span class="bracket">(</span>lst = list<span class="bracket">)</span> != <span class="keyword">null</span> && <span class="bracket">(</span>a = lst.elementData<span class="bracket">)</span> != <span class="keyword">null</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                <span class="keyword">if</span> <span class="bracket">(</span><span class="bracket">(</span>hi = fence<span class="bracket">)</span> <span class="bracket"><</span> <span class="number">0</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                    mc = lst.modCount;</li><li>                    hi = lst.size;</li><li>                <span class="bracket">}</span></li><li>                <span class="keyword">else</span></li><li>                    mc = expectedModCount;</li><li>                <span class="keyword">if</span> <span class="bracket">(</span><span class="bracket">(</span>i = index<span class="bracket">)</span> <span class="bracket">></span>= <span class="number">0</span> && <span class="bracket">(</span>index = hi<span class="bracket">)</span> <span class="bracket"><</span>= a.length<span class="bracket">)</span> <span class="bracket">{</span></li><li>                    <span class="keyword">for</span> <span class="bracket">(</span>; i <span class="bracket"><</span> hi; ++i<span class="bracket">)</span> <span class="bracket">{</span></li><li>                        <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span> <span class="builtin_var">E</span> e = <span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">)</span> a<span class="bracket">[</span>i<span class="bracket">]</span>;</li><li>                        action.accept<span class="bracket">(</span>e<span class="bracket">)</span>;</li><li>                    <span class="bracket">}</span></li><li>                    <span class="keyword">if</span> <span class="bracket">(</span>lst.modCount == mc<span class="bracket">)</span></li><li>                        <span class="keyword">return</span>;</li><li>                <span class="bracket">}</span></li><li>            <span class="bracket">}</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">long</span> estimateSize<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">return</span> <span class="bracket">(</span><span class="keyword">long</span><span class="bracket">)</span> <span class="bracket">(</span>getFence<span class="bracket">(</span><span class="bracket">)</span> - index<span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">public</span> <span class="keyword">int</span> characteristics<span class="bracket">(</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">return</span> Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;</li><li>        <span class="bracket">}</span></li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="description">@Override</span></li><li>    <span class="keyword">public</span> <span class="keyword">boolean</span> removeIf<span class="bracket">(</span>Predicate<span class="bracket"><</span>? <span class="keyword">super</span> <span class="builtin_var">E</span><span class="bracket">></span> filter<span class="bracket">)</span> <span class="bracket">{</span></li><li>        Objects.requireNonNull<span class="bracket">(</span>filter<span class="bracket">)</span>;</li><li>        <span class="comment">// figure out which elements are to be removed</span></li><li>        <span class="comment">// any exception thrown from the filter predicate at this stage</span></li><li>        <span class="comment">// will leave the collection unmodified</span></li><li>        <span class="keyword">int</span> removeCount = <span class="number">0</span>;</li><li>        <span class="keyword">final</span> BitSet removeSet = <span class="keyword">new</span> BitSet<span class="bracket">(</span>size<span class="bracket">)</span>;</li><li>        <span class="keyword">final</span> <span class="keyword">int</span> expectedModCount = modCount;</li><li>        <span class="keyword">final</span> <span class="keyword">int</span> size = <span class="keyword">this</span>.size;</li><li>        <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i=<span class="number">0</span>; modCount == expectedModCount && i <span class="bracket"><</span> size; i++<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>            <span class="keyword">final</span> <span class="builtin_var">E</span> element = <span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">)</span> elementData<span class="bracket">[</span>i<span class="bracket">]</span>;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span>filter.test<span class="bracket">(</span>element<span class="bracket">)</span><span class="bracket">)</span> <span class="bracket">{</span></li><li>                removeSet.set<span class="bracket">(</span>i<span class="bracket">)</span>;</li><li>                removeCount++;</li><li>            <span class="bracket">}</span></li><li>        <span class="bracket">}</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>modCount != expectedModCount<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="comment">// shift surviving elements left over the spaces left by removed elements</span></li><li>        <span class="keyword">final</span> <span class="keyword">boolean</span> anyToRemove = removeCount <span class="bracket">></span> <span class="number">0</span>;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span>anyToRemove<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">final</span> <span class="keyword">int</span> newSize = size - removeCount;</li><li>            <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i=<span class="number">0</span>, j=<span class="number">0</span>; <span class="bracket">(</span>i <span class="bracket"><</span> size<span class="bracket">)</span> && <span class="bracket">(</span>j <span class="bracket"><</span> newSize<span class="bracket">)</span>; i++, j++<span class="bracket">)</span> <span class="bracket">{</span></li><li>                i = removeSet.nextClearBit<span class="bracket">(</span>i<span class="bracket">)</span>;</li><li>                elementData<span class="bracket">[</span>j<span class="bracket">]</span> = elementData<span class="bracket">[</span>i<span class="bracket">]</span>;</li><li>            <span class="bracket">}</span></li><li>            <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> k=newSize; k <span class="bracket"><</span> size; k++<span class="bracket">)</span> <span class="bracket">{</span></li><li>                elementData<span class="bracket">[</span>k<span class="bracket">]</span> = <span class="keyword">null</span>;  <span class="comment">// Let gc do its work</span></li><li>            <span class="bracket">}</span></li><li>            <span class="keyword">this</span>.size = newSize;</li><li>            <span class="keyword">if</span> <span class="bracket">(</span>modCount != expectedModCount<span class="bracket">)</span> <span class="bracket">{</span></li><li>                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>            <span class="bracket">}</span></li><li>            modCount++;</li><li>        <span class="bracket">}</span></li><li></li><li>        <span class="keyword">return</span> anyToRemove;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="description">@Override</span></li><li>    <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>    <span class="keyword">public</span> <span class="keyword">void</span> replaceAll<span class="bracket">(</span>UnaryOperator<span class="bracket"><</span><span class="builtin_var">E</span><span class="bracket">></span> operator<span class="bracket">)</span> <span class="bracket">{</span></li><li>        Objects.requireNonNull<span class="bracket">(</span>operator<span class="bracket">)</span>;</li><li>        <span class="keyword">final</span> <span class="keyword">int</span> expectedModCount = modCount;</li><li>        <span class="keyword">final</span> <span class="keyword">int</span> size = <span class="keyword">this</span>.size;</li><li>        <span class="keyword">for</span> <span class="bracket">(</span><span class="keyword">int</span> i=<span class="number">0</span>; modCount == expectedModCount && i <span class="bracket"><</span> size; i++<span class="bracket">)</span> <span class="bracket">{</span></li><li>            elementData<span class="bracket">[</span>i<span class="bracket">]</span> = operator.apply<span class="bracket">(</span><span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">)</span> elementData<span class="bracket">[</span>i<span class="bracket">]</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>        <span class="keyword">if</span> <span class="bracket">(</span>modCount != expectedModCount<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>        modCount++;</li><li>    <span class="bracket">}</span></li><li></li><li>    <span class="description">@Override</span></li><li>    <span class="description">@SuppressWarnings</span><span class="bracket">(</span><span class="string">&quot;unchecked&quot;</span><span class="bracket">)</span></li><li>    <span class="keyword">public</span> <span class="keyword">void</span> sort<span class="bracket">(</span>Comparator<span class="bracket"><</span>? <span class="keyword">super</span> <span class="builtin_var">E</span><span class="bracket">></span> c<span class="bracket">)</span> <span class="bracket">{</span></li><li>        <span class="keyword">final</span> <span class="keyword">int</span> expectedModCount = modCount;</li><li>        Arrays.sort<span class="bracket">(</span><span class="bracket">(</span><span class="builtin_var">E</span><span class="bracket">[</span><span class="bracket">]</span><span class="bracket">)</span> elementData, <span class="number">0</span>, size, c<span class="bracket">)</span>;</li><li>        <span class="keyword">if</span> <span class="bracket">(</span>modCount != expectedModCount<span class="bracket">)</span> <span class="bracket">{</span></li><li>            <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException<span class="bracket">(</span><span class="bracket">)</span>;</li><li>        <span class="bracket">}</span></li><li>        modCount++;</li><li>    <span class="bracket">}</span></li><li><span class="bracket">}</span></li></ol></pre></fieldset></body></html>